package com.bascker.algorithm.practice.search.dfs.find_cheapest_price;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * 暴力解法：dfs 搜索所有可能路径 ==> TTL
 */
public class Solution {

    // key - startCity, value - dstCityList
    private Map<Integer, List<Data>> edges = new HashMap<>();

    // 最便宜的机票
    private int cheapest = Integer.MAX_VALUE;

    // 记录中转路径: 起点不记录在中转路径中
    private LinkedList<Integer> path = new LinkedList<>();

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        for (int[] f : flights) {
            List<Data> cityInfos = edges.getOrDefault(f[0], new ArrayList<>());
            cityInfos.add(new Data(f[1], f[2]));
            edges.put(f[0], cityInfos);
        }

        // 获取触发城市的目的地集合: 注意要 orDefault，防止 NPE，因为某个城市可能就没有航班
        List<Data> nextCity = edges.getOrDefault(src, new ArrayList<>());
        for (Data data : nextCity) {
            path.addLast(data.price);
            dfs(data, dst, k);
            path.removeLast();
        }

        // 注意做 -1 的处理，即无可达航班
        return cheapest == Integer.MAX_VALUE ? -1 : cheapest;
    }

    private void dfs(Data data, int dst, int k) {
        // 若路径长度 <= k + 1(因为从出发地到下一个城市不算中转) 时到达了 dst，则计算票价是否更便宜，然后返回
        if (data.city == dst && path.size() <= k + 1) {
            int totalPrice = cal();
            cheapest = Math.min(cheapest, totalPrice);
            return;
        }

        // 若路径长度到达 k 时还没到达dst，就返回
        if (path.size() > k + 1) {
            return;
        }

        // 注意要 orDefault，防止 NPE，因为某个城市可能就没有航班
        List<Data> nextCity = edges.getOrDefault(data.city, new ArrayList());
        for (Data next : nextCity) {
            path.addLast(next.price);
            dfs(next, dst, k);
            path.removeLast();
        }
    }

    // 求当前路径消耗的机票价格
    private int cal() {
        int sum = 0;
        for (int v : path) {
            sum += v;
        }

        return sum;
    }

    static class Data {

        // 城市
        public int city;

        // 票价
        public int price;

        public Data(int city, int price) {
            this.city = city;
            this.price = price;
        }
    }

}
